package listbyorder.access101_200.test147;

import listbyorder.utils.ListNode;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/12 9:48
 */
public class Solution1 {

    // 对链表进行插入排序
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode start = head;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        while (start.next != null) {
            ListNode temp = start.next;
            if (temp.val < start.val) {
                start.next = start.next.next;
                temp.next = null;
                ListNode pre = dummy;
                while (pre.next.val < temp.val) {
                    pre = pre.next;
                }
                temp.next = pre.next;
                pre.next = temp;
            } else {
                start = start.next;
            }
        }
        return dummy.next;
    }

}
